package club.xiaojiawei.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/29/22 9:36 PM
 * @question 435. 无重叠区间
 * @description 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 */
public class EraseOverlapIntervals435 {

    public static void main(String[] args) {
        EraseOverlapIntervals435 test = new EraseOverlapIntervals435();
        int result = test.eraseOverlapIntervals2(new int[][]{{0,2},{1,3},{2,4},{3,5},{4,6}});
        System.out.println("最小移除数："+result);
    }

    /**
     * 排序+贪心
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(logn)
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(point -> point[1]));
        int rear = intervals[0][1];
        int num = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < rear){
                num++;
            }else {
                rear = intervals[i][1];
            }
        }
        return num;
    }

    /**
     * 官方-dp（超时了）
     * 选出最多数量的区间，使得它们互不重叠
     * 时间复杂度O(n^2)
     * 空间复杂度：O(n)
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals2(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        int n = intervals.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }

}
